1. 20.1 xgboost算法原理

1.1. 学习目标

了解XGBoost的目标函数推导过程
知道XGBoost的回归树构建方法
知道XGBoost与GDBT的区别

XGBoost（Extreme Gradient Boosting）全名叫极端梯度提升树，XGBoost是集成学习方法的王牌，在Kaggle数据挖掘比赛中，大部分获胜者用了XGBoost。

XGBoost在绝大多数的回归和分类问题上表现的十分顶尖，本节将较详细的介绍XGBoost的算法原理。

1.2. 1 最优模型的构建方法

我们在前面已经知道，构建最优模型的一般方法是最小化训练数据的损失函数。

我们用字母 L表示损失，如下式：

其中，F是假设空间，假设空间是在已知属性和属性可能取值的情况下，对所有可能满足目标的情况的一种毫无遗漏的假设集合。

N是所有样本数，L代表损失函数，yi代表目标值，f(xi)代表预测值。

式（1.1）称为经验风险最小化，训练得到的模型复杂度较高。当训练数据较小时，模型很容易出现过拟合问题。

因此，为了降低模型的复杂度，常采用下式：

其中 J(f)为模型的复杂度，

式（2.1）称为结构风险最小化，结构风险最小化的模型往往对训练数据以及未知的测试数据都有较好的预测。

应用：

决策树的生成和剪枝分别对应了经验风险最小化和结构风险最小化，
XGBoost的决策树生成是结构风险最小化的结果，后续会详细介绍。

1.3. 2 XGBoost的目标函数推导

1.3.1. 2.1 目标函数确定

目标函数，即损失函数，通过最小化损失函数来构建最优模型。

由前面可知，损失函数应加上表示模型复杂度的正则项，且XGBoost对应的模型包含了多个CART树，因此，模型的目标函数为：

（3.1）式是正则化的损失函数；

其中yi是模型的实际输出结果，是模型的输出结果；

等式右边第一部分是模型的训练误差，第二部分是正则化项，这里的正则化项是K棵树的正则化项相加而来的。

1.3.2. 2.2 CART树的介绍

上图为第K棵CART树，确定一棵CART树需要确定两部分，

第一部分就是树的结构，这个结构将输入样本映射到一个确定的叶子节点上，记为fk(x;

第二部分就是各个叶子节点的值，q(x)表示输出的叶子节点序号，wq(x)表示对应叶子节点序号的值。

由定义得：

1.3.3. 2.3 树的复杂度定义

2.3.1 定义每课树的复杂度

XGBoost法对应的模型包含了多棵cart树，定义每棵树的复杂度：

其中T为叶子节点的个数，||w||为叶子节点向量的模。γ表示节点切分的难度，λ表示L2正则化系数。

2.3.2 树的复杂度举例

假设我们要预测一家人对电子游戏的喜好程度，考虑到年轻和年老相比，年轻更可能喜欢电子游戏，以及男性和女性相比，男性更喜欢电子游戏，故先根据年龄大小区分小孩和大人，然后再通过性别区分开是男是女，逐一给各人在电子游戏喜好程度上打分，如下图所示：

就这样，训练出了2棵树tree1和tree2，类似之前gbdt的原理，两棵树的结论累加起来便是最终的结论，所以：

小男孩的预测分数就是两棵树中小孩所落到的结点的分数相加：2 + 0.9 = 2.9。
爷爷的预测分数同理：-1 + （-0.9）= -1.9。

具体如下图所示：

如下例树的复杂度表示：

1.3.4. 2.4 目标函数推导

根据（3.1）式，共进行t次迭代的学习模型的目标函数为：

由前向分布算法可知，前t-1棵树的结构为常数

我们知道，泰勒公式的二阶导近似表示：

令为Δx , 则（3.5)式的二阶近似展开：

其中：

g_i和h_i分别表示预测误差对当前模型的一阶导和二阶导;

表示前t-1棵树组成的学习模型的预测误差。

当前模型往预测误差减小的方向进行迭代。

忽略（3.8）式常数项，并结合（3.4）式，得：

通过（3.2）式简化（3.9）式：

（3.10）式第一部分是对所有训练样本集进行累加，

此时，所有样本都是映射为树的叶子节点，

所以，我们换种思维，从叶子节点出发，对所有的叶子节点进行累加，得：

Gj 表示映射为叶子节点 j 的所有输入样本的一阶导之和，同理，H_j表示二阶导之和。

得：

对于第 t 棵CART树的某一个确定结构（可用q(x)表示），其叶子节点是相互独立的，

Gj 和Hj是确定量，因此，（3.12）可以看成是关于叶子节点w的一元二次函数。

最小化（3.12）式，得：

把（3.13）带入到（3.12），得到最终的目标函数：

（3.14）也称为打分函数(scoring function)，它是衡量树结构好坏的标准，

值越小，代表这样的结构越好。
我们用打分函数选择最佳切分点，从而构建CART树。

1.4. 3 XGBoost的回归树构建方法

1.4.1. 3.1 计算分裂节点

在实际训练过程中，当建立第 t 棵树时，XGBoost采用贪心法进行树结点的分裂：

从树深为0时开始：

对树中的每个叶子结点尝试进行分裂；
每次分裂后，原来的一个叶子结点继续分裂为左右两个子叶子结点，原叶子结点中的样本集将根据该结点的判断规则分散到左右两个叶子结点中；
新分裂一个结点后，我们需要检测这次分裂是否会给损失函数带来增益，增益的定义如下：

如果增益Gain>0，即分裂为两个叶子节点后，目标函数下降了，那么我们会考虑此次分裂的结果。

那么一直这样分裂，什么时候才会停止呢？

1.4.2. 3.2 停止分裂条件判断

情况一：上节推导得到的打分函数是衡量树结构好坏的标准，因此，可用打分函数来选择最佳切分点。首先确定样本特征的所有切分点，对每一个确定的切分点进行切分，切分好坏的标准如下：

Gain表示单节点obj与切分后的两个节点的树obj之差，
遍历所有特征的切分点，找到最大Gain的切分点即是最佳分裂点，根据这种方法继续切分节点，得到CART树。
若 γ 值设置的过大，则Gain为负，表示不切分该节点，因为切分后的树结构变差了。
- γ 值越大，表示对切分后obj下降幅度要求越严，这个值可以在XGBoost中设定。

情况二：当树达到最大深度时，停止建树，因为树的深度太深容易出现过拟合，这里需要设置一个超参数max_depth。

情况三：当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值，也会放弃此次分裂。这涉及到一个超参数:最小样本权重和，是指如果一个叶子节点包含的样本数量太少也会放弃分裂，防止树分的太细，这也是过拟合的一种措施。

1.5. 4 XGBoost与GDBT的区别

区别一：
- XGBoost生成CART树考虑了树的复杂度，
- GDBT未考虑，GDBT在树的剪枝步骤中考虑了树的复杂度。
区别二：
- XGBoost是拟合上一轮损失函数的二阶导展开，GDBT是拟合上一轮损失函数的一阶导展开，因此，XGBoost的准确性更高，且满足相同的训练效果，需要的迭代次数更少。
区别三：
- XGBoost与GDBT都是逐次迭代来提高模型性能，但是XGBoost在选取最佳切分点时可以开启多线程进行，大大提高了运行速度。

1.6. 5 小结

XGBoost的目标函数
知道XGBoost的回归树构建方法
XGBoost与GBDT的区别
- 区别一：
  - XGBoost生成CART树考虑了树的复杂度，
  - GBDT未考虑，GBDT在树的剪枝步骤中考虑了树的复杂度。
- 区别二：
  - XGBoost是拟合上一轮损失函数的二阶导展开，GDBT是拟合上一轮损失函数的一阶导展开，因此，XGBoost的准确性更高，且满足相同的训练效果，需要的迭代次数更少。
- 区别三：
  - XGBoost与GDBT都是逐次迭代来提高模型性能，但是XGBoost在选取最佳切分点时可以开启多线程进行，大大提高了运行速度。

20.1 xgboost算法原理